//
//  Sort_13.swift
//  ArithmeticClass7
//
//  Created by xiangzuhua on 2020/10/29.
//  Copyright © 2020 xiang. All rights reserved.
//

import Foundation

public class Sort_13: NSObject {
    
    // 字母相关桶排序
    func bucketSort(_ arr: inout [String] ) {
        // 100以内的若干个数，分成10个桶，每个桶进行快速排序，排序完成后，拼接成一个数组，即结果
    }
    
    // 计数排序
    class func countSort(_ arr: inout [Int],maxValue: Int) {
        let n = arr.count
        if n <= 1 {
            return
        }
        /*
         对于范围在0~maxValue之间的数组arr，先遍历每个数值在这个数组中出现的次数，
         用一个大小为maxValue + 1的数组以数值为下标，以数值的个数为值进行存储。
        */
        var numberCountArr = [Int](repeating: 0, count: maxValue + 1)
        for item in arr {
            numberCountArr[item] += 1
        }
        
        /*
         对numberCountArr中的值做一次处理，目标是以数组下标大小对应原始数组中元素的数值的大小，
         存储原始数组中小于等于这个下标的值的个数，
         如下标3存储的是原始数组中小于等于3的元素的个数
         */
        for (index, item) in numberCountArr.enumerated() {
            if index > 0 {
                numberCountArr[index] = numberCountArr[index - 1] + item
            }
        }
        
        /*
         创建一个与原数组大小一致的数组作为排序后的目标数组targetArr，然后对数据arr从后往前遍历，每拿到一个数值'X'，就以这个数值为下标，去numberCountArr数组中取下标对应存储的值'X-value'，'X-value'值的大小决定了'X'在targetArr数组的位置,比喻'X-value' = 7，那'X'在targetArr中的位置就是第7个,所以应该将'X'存到targetArr[6]，同时在这一次遍历结束后需要将'X-value'减一。接下来就是重复遍历处理，到最后遍历完，targetArr中就是想要的结果
         */
        var targetArr = [Int](repeating: 0, count: arr.count)
        for (_, item) in arr.enumerated().reversed() {
            let targetIndex = numberCountArr[item]
            targetArr[targetIndex - 1] = item
            numberCountArr[item] -= 1
        }
        arr = targetArr
    }
    
    // 基数排序 - 单词的排序
    class func  cardinalNumberSort(_ arr: inout [String]){
        // 获取数据中位数最多的字符串的位数值
        var number = 0
        for item in arr {
            if item.count > number {
                number = item.count
            }
        }
        
        // 补齐位数不够数据
        var newArr = [String]()
        for item in arr {
            if item.count < number {
                var polishingString = ""
                for _ in 1...number - item.count {
                    polishingString.append("#")
                }
                newArr.append(item.appending(polishingString))
            }else{
                newArr.append(item)
            }
        }
        
        // 创建26个桶
        var containerArr:[[String]] = [[String]](repeating:[String](), count: 26)
        for i in 0...number - 1 {
            for item in newArr {
                
                let index = item.index(item.startIndex, offsetBy: item.count - 1 - i )
                let cha = item[index]
                if cha == "#" {
                    containerArr[0].append(item)
                } else {
                    let targetIndex: Int = Int(cha.asciiValue! - 97)
                    containerArr[targetIndex].append(item)
                }
            }
            
            newArr.removeAll()
            
            for i in 0...25 {
                if containerArr[i].count > 0 {
                    newArr.append(contentsOf: containerArr[i])
                    containerArr[i].removeAll()
                }
            }
        }
        let characterSet = CharacterSet(charactersIn: "#")
        for (index,item) in newArr.enumerated(){
            let resultString = item.trimmingCharacters(in: characterSet)
            newArr[index] = resultString
        }
        arr = newArr
    }
}
